package com.learn._2list;


import com.learn.TestTool;

import java.util.Random;

public class LinkedList<T> implements List<T> {

    //头结点一开始就创建，为虚拟节点，这样在size变到0时不用做额外判空，减少不必要开销
    private LinkNode<T> head = new LinkNode<>();
    private LinkNode<T> last = head;
    private int curr;


    public static class LinkNode<T>{
        public T value;
        public LinkNode<T> next;
        public LinkNode<T> pre;


    }


    public LinkedList(){

    }


    /**
     *
     * @param idx
     * @return
     */
    @Override
    public T get(int idx) {
        LinkNode<T> res = getNode(idx);

        return res.value;
    }

    public  LinkNode<T> getNode(int idx) {
        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        LinkNode<T> res;


        if(idx > (curr >> 1)){
            res = last;
            idx = curr - idx - 1;
            int i = 0;
            while(i ++ < idx){
                res = res.pre;
            }
        }else{
            res = head;


            /*for(int i = 0;i <= idx;i ++){
                res = res.next;
            }*/
            int i = 0;
            while(i++ <= idx){
                res = res.next;
            }
            //TODO 要注意为什么不用被注释的代码，因为引入了减法操作，而这会比加法操作慢得多。这和cpu指令集的实现有关
            /*while(idx -- > -1){
                res = res.next;
            }*/
        }
        return res;
    }

    @Override
    public int indexOf(T obj) {

        if(obj == null){
            return -1;
        }
        LinkNode tmp = head;
        int idx = -1;
        while(tmp.next != null){
            tmp = tmp.next;
            idx ++;
            if(obj.equals(tmp.value)){
                return idx;
            }
        }
        return -1;
    }

    @Override
    public boolean contains(T obj) {
        return indexOf(obj) != -1;
    }

    @Override
    public boolean empty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return curr;
    }

    @Override
    public void add(T obj) {
        LinkNode<T> newNode = new LinkNode<>();
        newNode.value = obj;
        last.next = newNode;
        newNode.pre = last;
        last = newNode;
        curr ++;
    }

    /**
     * linked list不用移，但是需要找                      双链表可以倒着找优化
     * @param idx
     * @param obj
     */
    @Override
    public void add(int idx, T obj) {

        if(idx > curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        if(idx == curr){
            add(obj);
        }else{


            if(idx < (curr >> 1)) {
                LinkNode<T> tmp = head;
                int tmpIdx = 0;
                while (tmp.next != null) {
                    if (tmpIdx == idx) {
                        break;
                    }
                    tmp = tmp.next;
                    tmpIdx++;
                }
                insertAfter(tmp,obj);
            }else{
                LinkNode<T> tmp = last;
                idx = curr - idx - 1;
                int tmpIdx = 0;
                while (tmp.pre != null) {
                    if (tmpIdx == idx) {
                        break;
                    }
                    tmp = tmp.pre;
                    tmpIdx++;
                }
                insertBefore(tmp,obj);
            }

            curr ++;
        }
    }

    private void insertBefore(LinkNode<T> tmp, T obj) {

        LinkNode<T> newNode = new LinkNode<>();
        newNode.value = obj;

        newNode.pre = tmp.pre;
        newNode.next = tmp;
        newNode.pre.next = newNode;
        tmp.pre = newNode;
    }

    //保证tmp一定有后置
    private void insertAfter(LinkNode tmp, T obj) {
        LinkNode<T> newNode = new LinkNode<>();
        newNode.value = obj;

        newNode.next = tmp.next;
        newNode.pre = tmp;
        newNode.next.pre = newNode;
        tmp.next = newNode;
    }


    /**
     * linked list不用移，但是需要找
     *
     * @param obj
     */
    @Override
    public void remove(T obj) {

        LinkNode father = null;
        LinkNode tmp = head;
        boolean remove = false;
        while(tmp.next!= null){
            father = tmp;
            tmp = tmp.next;
            if(obj.equals(tmp.value)){
                remove = true;
                break;
            }
        }
        if(remove) {
            removeAfter(father);
            curr --;
        }
    }

    @Override
    public void remove(int idx) {

        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        if(idx < (curr >> 1)) {
            LinkNode<T> tmp = head;
            int tmpIdx = 0;
            while (tmp.next != null) {
                if (tmpIdx == idx) {
                    break;
                }
                tmp = tmp.next;
                tmpIdx++;
            }
            removeAfter(tmp);
        }else{
            LinkNode<T> tmp = last;
            idx = curr - idx - 1;
            int tmpIdx = 0;
            while (tmp.pre != null) {
                if (tmpIdx == idx) {
                    break;
                }
                tmp = tmp.pre;
                tmpIdx++;
            }
            remove(tmp);
        }
        curr --;
    }

    private void remove(LinkNode<T> tmp) {

        tmp.pre.next = tmp.next;
        if(tmp.next != null){
            tmp.next.pre = tmp.pre;
        }

    }

    //尾部没有哨兵，因此需要判空
    private void removeAfter(LinkNode<T> preNode) {
        if(preNode.next.next == null){
            last = preNode;
        }else{
            preNode.next.next.pre = preNode;
        }
        preNode.next = preNode.next.next;
        //该节点在java中自动释放
    }

    @Override
    public void set(int idx, T obj) {

        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }

        LinkNode<T> tmp = null;
        if(idx < (curr >> 1)) {
            tmp = head;
            int tmpIdx = 0;
            while (tmp.next != null) {
                if (tmpIdx == idx) {
                    break;
                }
                tmp = tmp.next;
                tmpIdx++;
            }
            tmp = tmp.next;
        }else{
            tmp = last;
            idx = curr - idx - 1;
            int tmpIdx = 0;
            while (tmp.pre != null) {
                if (tmpIdx == idx) {
                    break;
                }
                tmp = tmp.pre;
                tmpIdx++;
            }

        }
        tmp.value = obj;
    }

    @Override
    public void clear() {
        head.next = null;
        last = head;
        curr = 0;
    }



    public static void main(String[] args) {
        java.util.LinkedList javaList = new java.util.LinkedList<>();
        LinkedList arrayList = new LinkedList();


        int num = 100000;
        int range = 1000000;
        int circleNum = 100;
        Integer[] array = new Integer[num];
        Random rand = new Random();
        int tmp = 0;
        int tmpNum = num;
        while(tmpNum -- > 0){
            array[tmp ++] = rand.nextInt(range);
        }

        for(Integer i :array){
            javaList.add(i);
            arrayList.add(i);
        }


        //查找测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.contains(i);
            }
        },1,"java contains ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.contains(i);
            }
        },1,"my contains ");*/


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.get(i);
            }
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.get(i);
            }
        },1,"my  ");




        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.indexOf(i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.indexOf(i);
            }
        },1,"java ");*/

        //增测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                javaList.add(i,i);
            }
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                arrayList.add(i,i);
            }
        },1,"my  ");*/






        //修改测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < num; i ++){
                arrayList.set(i,i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < num; i ++){
                javaList.set(i,i);
            }
        },1,"java ");*/



        //删测试

       /* TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                javaList.add(i);
            }

            for(int i = 0;i < num; i ++){
                javaList.remove(new Integer(i));
            }
            javaList.clear();
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                arrayList.add(i);
            }

            for(int i = 0;i < num; i ++){
                arrayList.remove(new Integer(i));
            }
            arrayList.clear();
        },1,"my  ");*/








    }
}
